package 剑指offer_leetcode;

import java.util.Stack;

/**
 * JZ33二叉搜索树的后序遍历序列
 */
public class 剑指Offer33_二叉搜索树的后序遍历序列 {
    public boolean verifyPostorder(int[] postorder) {
        int root = Integer.MAX_VALUE;
        Stack<Integer> s = new Stack<>();
        for(int i=postorder.length-1;i>=0;i--){
            if(postorder[i]>root)   return false;
            while(!s.isEmpty() && s.peek()>postorder[i])
                root = s.pop();
            s.push(postorder[i]);
        }
        return true;
    }
}
